{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "601b9d7f-4c4f-4e8d-ba27-6122074ceec4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated Jaccard for data1 and data2 is 0.7109375\n",
      "Actual Jaccard for data1 and data2 is 0.7142857142857143\n"
     ]
    }
   ],
   "source": [
    "from datasketch import MinHash\n",
    "\n",
    "data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',\n",
    "        'estimating', 'the', 'similarity', 'between', 'datasets']\n",
    "data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',\n",
    "        'estimating', 'the', 'similarity', 'between', 'documents']\n",
    "\n",
    "m1, m2 = MinHash(), MinHash()\n",
    "for d in data1:\n",
    "    m1.update(d.encode('utf8'))\n",
    "for d in data2:\n",
    "    m2.update(d.encode('utf8'))\n",
    "print(\"Estimated Jaccard for data1 and data2 is\", m1.jaccard(m2))\n",
    "\n",
    "s1 = set(data1)\n",
    "s2 = set(data2)\n",
    "actual_jaccard = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))\n",
    "print(\"Actual Jaccard for data1 and data2 is\", actual_jaccard)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ebcbc237-0de8-431f-90be-90f629079bf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Approximate neighbours with Jaccard similarity > 0.5 ['m3', 'm2']\n"
     ]
    }
   ],
   "source": [
    "from datasketch import MinHash, MinHashLSH\n",
    " \n",
    "set1 = set(['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',\n",
    "            'estimating', 'the', 'similarity', 'between', 'datasets'])\n",
    "set2 = set(['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',\n",
    "            'estimating', 'the', 'similarity', 'between', 'documents'])\n",
    "set3 = set(['minhash', 'is', 'probability', 'data', 'structure', 'for',\n",
    "            'estimating', 'the', 'similarity', 'between', 'documents'])\n",
    " \n",
    "m1 = MinHash(num_perm=128)\n",
    "m2 = MinHash(num_perm=128)\n",
    "m3 = MinHash(num_perm=128)\n",
    "for d in set1:\n",
    "    m1.update(d.encode('utf8'))\n",
    "for d in set2:\n",
    "    m2.update(d.encode('utf8'))\n",
    "for d in set3:\n",
    "    m3.update(d.encode('utf8'))\n",
    " \n",
    "# Create LSH index\n",
    "lsh = MinHashLSH(threshold=0.5, num_perm=128)\n",
    "lsh.insert(\"m2\", m2)\n",
    "lsh.insert(\"m3\", m3)\n",
    "result = lsh.query(m1)\n",
    "print(\"Approximate neighbours with Jaccard similarity > 0.5\", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3909af0d-e757-4c98-88cd-03b85f2af4f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "Top 2 candidates ['m3', 'm2']\n"
     ]
    }
   ],
   "source": [
    "from datasketch import MinHashLSHForest, MinHash\n",
    " \n",
    "data1 = ['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',\n",
    "        'estimating', 'the', 'similarity', 'between', 'datasets']\n",
    "data2 = ['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',\n",
    "        'estimating', 'the', 'similarity', 'between', 'documents']\n",
    "data3 = ['minhash', 'is', 'probability', 'data', 'structure', 'for',\n",
    "        'estimating', 'the', 'similarity', 'between', 'documents']\n",
    " \n",
    "# Create MinHash objects\n",
    "m1 = MinHash(num_perm=128)\n",
    "m2 = MinHash(num_perm=128)\n",
    "m3 = MinHash(num_perm=128)\n",
    "for d in data1:\n",
    "    m1.update(d.encode('utf8'))\n",
    "for d in data2:\n",
    "    m2.update(d.encode('utf8'))\n",
    "for d in data3:\n",
    "    m3.update(d.encode('utf8'))\n",
    " \n",
    "# Create a MinHash LSH Forest with the same num_perm parameter\n",
    "forest = MinHashLSHForest(num_perm=128)\n",
    " \n",
    "# Add m2 and m3 into the index\n",
    "forest.add(\"m2\", m2)\n",
    "forest.add(\"m3\", m3)\n",
    " \n",
    "# IMPORTANT: must call index() otherwise the keys won't be searchable\n",
    "forest.index()\n",
    "# Check for membership using the key\n",
    "print(\"m2\" in forest)\n",
    "print(\"m3\" in forest)\n",
    "# Using m1 as the query, retrieve top 2 keys that have the higest Jaccard\n",
    "result = forest.query(m1, 2)\n",
    "print(\"Top 2 candidates\", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e351c000-494e-4030-b987-dbfe9afb641b",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Building prefix dict from the default dictionary ...\n",
      "Loading model from cache C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\jieba.cache\n",
      "Loading model cost 0.663 seconds.\n",
      "Prefix dict has been built successfully.\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "doc_0 is similar to ['doc_0', 'doc_3']\n",
      "doc_3 is similar to ['doc_3', 'doc_0']\n"
     ]
    }
   ],
   "source": [
    "import jieba\n",
    "from datasketch import MinHash, MinHashLSH\n",
    "\n",
    "# 示例数据\n",
    "documents = [\n",
    "    \"今天天气真好，适合出去玩。\",\n",
    "    \"今天天气不错，可以出去玩。\",\n",
    "    \"明天有大雨，最好不要外出。\",\n",
    "    \"今天天气真好，适合出游。\",\n",
    "    \"明天有暴雨，尽量留在家里。\"\n",
    "]\n",
    "\n",
    "# 初始化jieba分词器\n",
    "jieba.initialize()\n",
    "\n",
    "# 创建MinHash和LSH对象\n",
    "lsh = MinHashLSH(threshold=0.5, num_perm=128)\n",
    "minhashes = {}\n",
    "\n",
    "# 处理文本，计算MinHash\n",
    "for i, doc in enumerate(documents):\n",
    "    words = jieba.cut(doc)\n",
    "    m = MinHash(num_perm=128)\n",
    "    for word in words:\n",
    "        m.update(word.encode('utf8'))\n",
    "    minhashes[i] = m\n",
    "    lsh.insert(f\"doc_{i}\", m)\n",
    "\n",
    "# 查找重复文档\n",
    "duplicates = {}\n",
    "for i, minhash in minhashes.items():\n",
    "    result = lsh.query(minhash)\n",
    "    if len(result) > 1:\n",
    "        duplicates[f\"doc_{i}\"] = result\n",
    "\n",
    "# 输出结果\n",
    "for doc_id, similar_ids in duplicates.items():\n",
    "    print(f\"{doc_id} is similar to {similar_ids}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5f1f4a6-8f2b-42aa-a7f1-fc7fdf899b04",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
